#ifndef __LINKLIST_H__
#define __LINKLIST_H__

/*
==============================================================================

LinkList

Circular linked list template, double linked

==============================================================================
*/

namespace inf {

    template< typename Type >
    class LinkList
    {
    public:
                            LinkList( void );
                            ~LinkList( void );

        int					size( void ) const;
        void				clear( void );

        bool				empty( void ) const;
        bool				in_list( void ) const;

        void				insert_before( LinkList &node );
        void				insert_after( LinkList &node );
        void				add_to_end( LinkList &node );
        void				add_to_front( LinkList &node );

        void				remove( void );

        Type *				get_next( void ) const;
        Type *				get_prev( void ) const;

        Type *				get_owner( void ) const;
        void				set_owner( Type *object );

        LinkList *		list_head( void ) const;
        LinkList *		next_node( void ) const;
        LinkList *		prev_node( void ) const;

    private:
        LinkList *		head;
        LinkList *		next;
        LinkList *		prev;
        Type *			owner;
    };

    /*
    ================
    LinkList<Type>::LinkList

    Node is initialized to be the head of an empty list
    ================
    */
    template< typename Type >
    LinkList<Type>::LinkList( void ) {
        owner	= NULL;
        head	= this;	
        next	= this;
        prev	= this;
    }

    /*
    ================
    LinkList<Type>::~LinkList

    Removes the node from the list, or if it's the head of a list, removes
    all the nodes from the list.
    ================
    */
    template< typename Type >
    LinkList<Type>::~LinkList( void ) {
        clear();
    }

    /*
    ================
    LinkList<Type>::empty

    Returns true if the list is empty.
    ================
    */
    template< typename Type >
    bool LinkList<Type>::empty( void ) const {
        return head->next == head;
    }

    /*
    ================
    LinkList<Type>::in_list

    Returns true if the node is in a list.  If called on the head of a list, will always return false.
    ================
    */
    template< typename Type >
    bool LinkList<Type>::in_list( void ) const {
        return head != this;
    }

    /*
    ================
    LinkList<Type>::size

    Returns the number of nodes in the list.
    ================
    */
    template< typename Type >
    int LinkList<Type>::size( void ) const {
        LinkList<Type>	*node;
        int					num;

        num = 0;
        for( node = head->next; node != head; node = node->next ) {
            num++;
        }

        return num;
    }

    /*
    ================
    LinkList<Type>::clear

    If node is the head of the list, clears the list.  Otherwise it just removes the node from the list.
    ================
    */
    template< typename Type >
    void LinkList<Type>::clear( void ) {
        if ( head == this ) {
            while( next != this ) {
                next->remove();
            }
        } else {
            remove();
        }
    }

    /*
    ================
    LinkList<Type>::remove

    Removes node from list
    ================
    */
    template< typename Type >
    void LinkList<Type>::remove( void ) {
        // don't call remove() on the head element, or head needs to be updated in all the links
        assert( empty() || head != this );

        prev->next = next;
        next->prev = prev;

        next = this;
        prev = this;
        head = this;
    }

    /*
    ================
    LinkList<Type>::insert_before

    Places the node before the existing node in the list.  If the existing node is the head,
    then the new node is placed at the end of the list.
    ================
    */
    template< typename Type >
    void LinkList<Type>::insert_before( LinkList &node ) {
        remove();

        next		= &node;
        prev		= node.prev;
        node.prev	= this;
        prev->next	= this;
        head		= node.head;
    }

    /*
    ================
    LinkList<Type>::insert_after

    Places the node after the existing node in the list.  If the existing node is the head,
    then the new node is placed at the beginning of the list.
    ================
    */
    template< typename Type >
    void LinkList<Type>::insert_after( LinkList &node ) {
        remove();

        prev		= &node;
        next		= node.next;
        node.next	= this;
        next->prev	= this;
        head		= node.head;
    }

    /*
    ================
    LinkList<Type>::add_to_end

    Adds node at the end of the list
    ================
    */
    template< typename Type >
    void LinkList<Type>::add_to_end( LinkList &node ) {
        insert_before( *node.head );
    }

    /*
    ================
    LinkList<Type>::add_to_front

    Adds node at the beginning of the list
    ================
    */
    template< typename Type >
    void LinkList<Type>::add_to_front( LinkList &node ) {
        insert_after( *node.head );
    }

    /*
    ================
    LinkList<Type>::list_head

    Returns the head of the list.  If the node isn't in a list, it returns
    a pointer to itself.
    ================
    */
    template< typename Type >
    LinkList<Type> *LinkList<Type>::list_head( void ) const {
        return head;
    }

    /*
    ================
    LinkList<Type>::next

    Returns the next object in the list, or NULL if at the end.
    ================
    */
    template< typename Type >
    Type *LinkList<Type>::get_next( void ) const {
        if ( !next || ( next == head ) ) {
            return NULL;
        }
        return next->owner;
    }

    /*
    ================
    LinkList<Type>::prev

    Returns the previous object in the list, or NULL if at the beginning.
    ================
    */
    template< typename Type >
    Type *LinkList<Type>::get_prev( void ) const {
        if ( !prev || ( prev == head ) ) {
            return NULL;
        }
        return prev->owner;
    }

    /*
    ================
    LinkList<Type>::next_node

    Returns the next node in the list, or NULL if at the end.
    ================
    */
    template< typename Type >
    LinkList<Type> *LinkList<Type>::next_node( void ) const {
        if ( next == head ) {
            return NULL;
        }
        return next;
    }

    /*
    ================
    LinkList<Type>::prev_node

    Returns the previous node in the list, or NULL if at the beginning.
    ================
    */
    template< typename Type >
    LinkList<Type> *LinkList<Type>::prev_node( void ) const {
        if ( prev == head ) {
            return NULL;
        }
        return prev;
    }

    /*
    ================
    LinkList<Type>::owner

    Gets the object that is associated with this node.
    ================
    */
    template< typename Type >
    Type *LinkList<Type>::get_owner( void ) const {
        return owner;
    }

    /*
    ================
    LinkList<Type>::set_owner

    Sets the object that this node is associated with.
    ================
    */
    template< typename Type >
    void LinkList<Type>::set_owner( Type *object ) {
        owner = object;
    }


    /*
    ============
    operator==( LinkList< Type >, LinkList< Type > )
    ============
    */
    template< typename Type >
    bool operator==( const LinkList< Type >& lhs, const LinkList< Type >& rhs ) {
        return (	lhs.owner() == rhs.owner() && 
            lhs.list_head() == rhs.list_head() &&
            lhs.next_node() == rhs.next_node() &&
            lhs.prev_node() == rhs.prev_node()
            );
    }


}   // ::inf

#endif /* !__LINKLIST_H__ */
